package class07_heapRelated;

import java.util.Comparator;
import java.util.PriorityQueue;

public class HeapAndHeapSort {

    public static void swap(int[] arr, int index1, int index2)
    {

//        arr[index1] = arr[index1]^arr[index2];
//        arr[index2] = arr[index1]^arr[index2];
//        arr[index1] = arr[index1]^arr[index2];
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
    public static void heapUpAdjust(int[] arr, int index){
        /*
        * arr 数组表示的堆
        * index 插入的位置; 不一定是0是因为可能只是对一个局部进行操作
        * */
        int fatherIndex = (index-1)/2;
        while(index>0 && arr[fatherIndex]<arr[index]){ // 一直到根，或者其父比他大
            swap(arr, index, fatherIndex);
            index = fatherIndex;
            fatherIndex = (index-1)/2;
        }
    }

    public static void heapDownAdjust(int[] arr, int heapLen, int index){
        int biggerChildIndex;
        while(index*2+1<heapLen)//左儿子在队列中
        {
            biggerChildIndex = index*2+1;

            //若右儿子比左儿子大，将大儿子更新
            if(index*2+2<heapLen && arr[index*2+2]>arr[biggerChildIndex]){
                biggerChildIndex = index*2+2;
            }

            //比较较大的儿子与父节点的大小，儿子比较大父亲就下沉
            if(arr[index]<arr[biggerChildIndex]) {
                swap(arr,index,biggerChildIndex);
                index = biggerChildIndex;
            }
            else break;//否则就停住
        }
    }

    public static void buildHeap(int[] arr){ //经典方法 O(N*log(N))
        for (int i = 0;  i <arr.length; i++) { //O(N)
                heapUpAdjust(arr,i); //自上而下对所有结点向上调整 O(log(N))
                //大量的结点调整的层数多 O(log(N))
        }
    }

    public static void buildHeapN(int[] arr){//更快方法 O(N)
        //只有所有数全部给你可以这样搞，一个一个加进来只能用上面的经典方法
        for (int i = arr.length-1; i>=0; i--){
            heapDownAdjust(arr,arr.length,i);
            //大量的结点调整的层数少 O(N)
        }
    }

    public static void heapSort(int[] arr){
        buildHeap(arr);
        for(int i=arr.length-1; i>0; i--){
            swap(arr,0,i);
            heapDownAdjust(arr, i,0);
        }
    }

    public static void heapSortWithPriorityQueue(int[] arr){
        PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

        for(int i=0; i<arr.length; i++){
            heap.add(arr[i]);
        }

        for (int i = arr.length-1; i >= 0 ; i--) {
            arr[i] = heap.poll();
        }
    }

    public static int[] randomArr (int maxLen,int maxValue)
    {
        int len = (int)(maxLen*Math.random());
        int[] arr =new int[len];

        for(int i = 0; i<len; i++)
        {
            arr[i] = (int)(maxValue*Math.random());
        }
        return arr;
    }

    public static boolean isOrder(int[] arr)
    {
        int len = arr.length;

        for(int i = 0; i<len-1; i++)
        {
            if(arr[i+1]<arr[i])
            {
                return false;
            }
        }
        return true;
    }

    public static boolean isHeap(int[] arr, int heapLen){
        int index=0;
        while(index*2+1<heapLen){
            int left_child = index*2+1;
            int right_child = index*2+2;
            if(arr[index]<arr[left_child]) return false;
            if(right_child<heapLen && arr[index]<arr[right_child]) return false;
            index++;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr = randomArr(100, 100);
                //{56, 65, 47, 85, 89, 84, 61, 19, 30, 64, 91, 0 ,77, 89, 41, 80, 74, 40, 3, 89, 96, 2, 20, 61, 40, 43, 53, 96, 77, 1, 21};//randomArr(100, 100);//{33, 39, 36, 81, 88};//
        for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}
        //heapSort(arr);
        buildHeapN(arr);
        System.out.println("\n"+isHeap(arr,arr.length));
        for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}
        System.out.println("\n"+isOrder(arr));
    }
}